package 剑指offer;

public class Offer33_JZ23 {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) {
            return false;
        }

        return recurr(sequence, 0, sequence.length-1);
    }

    public boolean recurr(int[] sequence, int i, int j){
        if(i>=j) {
            return true;
        }
        int p = i;
        while(sequence[p] < sequence[j]) {
            p++;
        }
        int m = p;
        while(sequence[p] > sequence[j]) {
            p++;
        }
        return p==j && recurr(sequence, i, m-1) && recurr(sequence, m, j-1);
    }

    // 未通过
        public static boolean VerifySquenceOfBST2(int [] sequence) {
            return verify(sequence, 0, sequence.length - 1);

        }
        public static boolean verify(int[] sequence, int begin, int end) {
            if (begin-end>= 0) {
                return true;
            }
            int root = sequence[end];

            int i=begin;
            for (; i<=end; ++i) {
                if (sequence[i] > root) {
                    break;
                }
            }

            int j = i;
            for (; j<=end; ++j) {
                if (sequence[j] < root) {
                    return false;
                }
            }
            boolean left = true;
            if (i > begin) {
                left = verify(sequence, begin, i-1);
            }

            boolean right = true;
            if (i < end) {
                right = verify(sequence, i+1, end);
            }
            return left && right;
        }

}
